package leetcode.code438;

import java.util.ArrayList;
import java.util.List;

public class Solution2 extends Solution438 {

	@Override
	public List<Integer> findAnagrams(String s, String p) {
		List<Integer> result = new ArrayList<>();
		if (p.length() > s.length()) {
			return result;
		}
		char[] ss = s.toCharArray();// s串
		char[] pp = p.toCharArray();// p串
		int[] dic = new int[128];// 字典
		for (int i = 0; i < pp.length; i++) {
			dic[pp[i]] += 1;// 为p创建字典，记录p中所有字符的个数，创建了128的长度，省掉了减法操作
		}
		int ft = 0;// fast 快针
		int sw = 0;// slow 慢针
		int lenp = pp.length;// 找到答案的结束标识
		int count = 0;// ft-sw定长，count是在这个之间有效数量
		while (ft < lenp) {// 创建初始窗口
			int a = dic[ss[ft]] -= 1;// s串中初始窗口里，出现的字符抵消字典，滑入做减法，滑出做加法
			if (a >= 0) {// 一个曾经被加入到字典的有效字符，在减少1后才能大于0
				count++;// 记录有效的个数
			}
			ft++;// 快针向前
		}
		if (count == lenp) {// 初始窗口中的字符正好够字典，这就是一个答案
			result.add(sw);
		}
		while (ft < ss.length) {// 开始滑动窗口
			int a = dic[ss[sw]] += 1;// 从窗口中将最左端一个字符移除，移除会使得dic中缺少的字符增加一个，滑出做加法
			if (a > 0) {// 移除的是一个有效字符，有效字符少了一个
				count--;
			}
			int b = dic[ss[ft]] -= 1;// 右侧进入，滑入做减法
			if (b >= 0) {
				count++;
			}
			sw++;
			ft++;
			if (count == lenp) {// 巧了，是答案，记录开头位置
				result.add(sw);
			}
		}
		return result;
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

//
//		System.out.println((int) 'a' - 'a');
//		System.out.println((int) 'z' - 'a');
//		System.out.println('z' - 'a');
	}

}
